class Solution:
    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:
        grid = [[0 for _ in range(m)] for _ in range(n)]
        for x, y in broken: grid[x][y] = 1
        @cache
        def getNum(idx, constraints):
            if idx == n-1:
                cnt = 0
                ans = 0
                for x in constraints:
                    if x == 1: cnt = 0
                    if x == 0:
                        cnt += 1
                        if cnt == 2:
                            ans += 1
                            cnt = 0
                return ans
            ans = 0
            new_constraints = grid[idx+1]
            old_constraints = list(constraints)
            possible_pos = [i for i, val in enumerate(constraints) if val == 0]
            vertical = []
            for item in possible_pos:
                if new_constraints[item] == 0: vertical.append(item)
            for i in range(2**len(vertical)):
                current_ans = 0
                tmp = []
                pos = 0
                while i:
                    if i % 2: tmp.append(vertical[pos])
                    pos += 1
                    i //= 2
                for item in tmp:
                    old_constraints[item] = 1
                    new_constraints[item] = 1
                cnt = 0
                for x in old_constraints:
                    if x == 1: cnt = 0
                    if x == 0:
                        cnt += 1
                        if cnt == 2:
                            current_ans += 1
                            cnt = 0
                current_ans += getNum(idx+1, tuple(new_constraints)) + len(tmp)
                ans = max(ans, current_ans)
                for item in tmp:
                    old_constraints[item] = 0
                    new_constraints[item] = 0
            return ans
        return getNum(0, tuple(grid[0]))
